package junior.回溯法;
/**
 * 框架：n个元素中取 r 个， 做允许重复组合，模拟集装箱给轮船的分配。
 * 构造长度为2的 1-2-3 向量（模拟3艘船），求出全部的解空间（每个解的长度模拟集装箱）
 * 解空间：1-2-3的全部组合，代表集装箱分配给每个船的全部情况
 */
public class 装载问题012三船 {
    static int[] stack = new int[10000000];
    static int top = 0;
    static int total = 0;
    // static int[] shipCapacitys = {47,61,62};;
    // static int[] containerWeight = {7,12,9,18,9,7,14,9,12,13,17,8,15,14,6};
    static int[] shipCapacitys = {38,40,62};;
    static int[] containerWeight = {14,15,16,17,19,17,19,23};
    public static void main(String[] args) {
        int a =0,b=0;
        for (int i= 0; i < containerWeight.length; i++) {
            a += containerWeight[i];
            if(i<3)
                b += shipCapacitys[i];
        }
        System.out.println("集装箱个数："+containerWeight.length);
        System.out.println("集装箱总重量："+a);
        System.out.println("轮船总重量："+b);
        fun(0);
        System.out.println("方案总数："+total);
    }

    public static void fun(int n){
        if(n == containerWeight.length){
            int[] load = new int[3];
            for (int i = 0; i < containerWeight.length; i++) {
                    load[stack[i]] += containerWeight[i];
            }
            if(load[0] <= shipCapacitys[0] && load[1] <= shipCapacitys[1]  && load[2] <= shipCapacitys[2]){
                // for (int i = 0; i < top; i++) {
                //     System.out.print(stack[i]+"\t");
                // }
                // System.out.println();
                total++;
            }
            return;
        }
        for (int i = 0; i < 3; i++) {
            stack[top++] = i;
            fun(n+1);
            top--;
        }
    }
}
